package com.leetcode.algorithm.y18.m05;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import com.leetcode.algorithm.common.ListNode;

/**
 * leetcode-cn.com
 * 121. 买卖股票的最佳时机
 * 122. 买卖股票的最佳时机 II
 * 125. 验证回文串
 * 136. 只出现一次的数字
 * 141. 环形链表
 * 160. 相交链表
 * 167.两数之和 II - 输入有序数组
 * 168. Excel表列名称
 * 169. 求众数
 * 171. Excel表列序号
 * @author dengjie213@126.com
 * 2018年5月8日 上午12:06:40
 */
public class MySolution0508 {

	/**
	 * 121. 买卖股票的最佳时机 
	 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
	 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
	 * 注意你不能在买入股票前卖出股票。
	 * 
	 * 示例 1:
	 * 输入: [7,1,5,3,6,4] 
	 * 输出: 5 
	 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
	 * 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 
	 * 
	 * 示例 2:
	 * 输入: [7,6,4,3,1] 
	 * 输出: 0 
	 * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {
		if (prices.length == 0) {
			return 0;
		}
		int min = prices[0];
		int maxProfit = 0;
		for (int i = 1; i < prices.length; i++) {
			if (prices[i] - min > maxProfit) {
				maxProfit = prices[i] - min;
			}
			if (prices[i] < min) {
				min = prices[i];
			}
		}
		return maxProfit;
	}

	/**
	 * 122. 买卖股票的最佳时机 II 
	 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
	 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
	 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
	 * 
	 * 示例 1:
	 * 输入: [7,1,5,3,6,4] 
	 * 输出: 7 
	 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出,
	 * 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出,
	 * 这笔交易所能获得利润 = 6-3 = 3 。 
	 * 
	 * 示例 2:
	 * 输入: [1,2,3,4,5] 
	 * 输出: 4 
	 * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出,
	 * 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
	 * 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 
	 * 
	 * 示例 3:
	 * 输入: [7,6,4,3,1] 
	 * 输出: 0 
	 * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
	 * 
	 * @param prices
	 * @return
	 */
	public int maxStockProfit(int[] prices) {
		if (prices.length <= 1) {
			return 0;
		}
		int sumProfit = 0;
		int i = 0;
		while (i < prices.length - 1) {
			if (prices[i] < prices[i + 1]) {
				sumProfit += prices[i + 1] - prices[i];
			}
			i++;
		}
		return sumProfit;
	}

	/**
	 * 125. 验证回文串 
	 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
	 * 说明：本题中，我们将空字符串定义为有效的回文串。
	 * 
	 * 示例 1:
	 * 输入: "A man, a plan, a canal: Panama" 
	 * 输出: true 
	 * 
	 * 示例 2:
	 * 输入: "race a car" 
	 * 输出: false
	 * 
	 * @param s
	 * @return
	 */
	public boolean isPalindrome(String s) {
		if ("".equals(s)) {
			return true;
		}
		char[] chars = s.toCharArray();
		int begin = 0;
		int end = chars.length-1;
		while (begin < end) {
			while (begin < end && !Character.isLetterOrDigit(chars[begin])) {
				begin++;
			}
			while (begin < end && !Character.isLetterOrDigit(chars[end])) {
				end--;
			}
			if (Character.toLowerCase(chars[begin]) != Character.toLowerCase(chars[end])) {
				return false;
			}else {
				begin++;
				end--;
			}
		}
		return true;
	}

	/**
	 * 136. 只出现一次的数字 
	 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
	 * 
	 * 说明：
	 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
	 * 
	 * 示例 1:
	 * 输入: [2,2,1] 
	 * 输出: 1 
	 * 
	 * 示例 2:
	 * 输入: [4,1,2,1,2] 
	 * 输出: 4
	 * 
	 * @param nums
	 * @return
	 */
	public int singleNumber(int[] nums) {
		// 最简洁的办法是异或运算
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(nums[i])) {
				map.remove(nums[i]);
			}else {
				map.put(nums[i], i);
			}
		}
		return map.keySet().iterator().next();
	}

	/**
	 * 141. 环形链表 
	 * 给定一个链表，判断链表中是否有环。 
	 * 进阶： 你能否不使用额外空间解决此题？
	 * 
	 * @param head
	 * @return
	 */
	public boolean hasCycle(ListNode head) {
		if (head == null) {
			return false;
		}
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		ListNode cur = head;
		while (cur.next != null) {
			int hashCode = cur.next.hashCode();
			if (map.containsKey(hashCode)) {
				return true;
			} else {
				map.put(hashCode, 0);
			}
			cur = cur.next;
		}
		return false;
	}

	/**
	 * 171. Excel表列序号 
	 * 给定一个Excel表格中的列名称，返回其相应的列序号。
	 * 
	 * 例如，
	 * A -> 1 
	 * B -> 2 
	 * C -> 3 
	 * ... 
	 * Z -> 26 
	 * AA -> 27 
	 * AB -> 28 
	 * ... 
	 * 
	 * 示例 1:
	 * 输入: "A" 
	 * 输出: 1 
	 * 
	 * 示例 2:
	 * 输入: "AB" 
	 * 输出: 28
	 * 
	 * 示例 3:
	 * 输入: "ZY" 
	 * 输出: 701
	 * 
	 * @param s
	 * @return
	 */
	public int titleToNumber(String s) {
		char[] chars = s.toCharArray();
		int idx = 0;
		for (int i = 0; i < chars.length; i++) {
			idx = idx*26 + (chars[i]-'A'+1);
		}
		return idx;
	}

	/**
	 * 168. Excel表列名称 
	 * 给定一个正整数，返回它在Excel表中相对应的列名称。
	 * 
	 * 例如，
	 * 1 -> A 
	 * 2 -> B 
	 * 3 -> C 
	 * ... 
	 * 26 -> Z 
	 * 27 -> AA 
	 * 28 -> AB ... 
	 * 
	 * 示例 1:
	 * 输入: 1 
	 * 输出: "A" 
	 * 
	 * 示例 2:
	 * 输入: 28 
	 * 输出: "AB" 
	 * 
	 * 示例 3:
	 * 输入: 701 
	 * 输出: "ZY"
	 * 
	 * @param n
	 * @return
	 */
	public String convertToTitle(int n) {
		//A 1
		//B 2
		//Z 26
		//AA 27
		StringBuffer sb = new StringBuffer();
		while (n > 0) {
			sb.append((char) ((n - 1) % 26 + 'A'));
			n = (n - (n - 1) % 26) / 26;
		}
		return sb.reverse().toString();
	}

	/**
	 * 169. 求众数 
	 * 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
	 * 
	 * 你可以假设数组是非空的，并且给定的数组总是存在众数。
	 * 
	 * 示例 1:
	 * 输入: [3,2,3] 
	 * 输出: 3 
	 * 
	 * 示例 2:
	 * 输入: [2,2,1,1,1,2,2] 
	 * 输出: 2
	 * 
	 * @param nums
	 * @return
	 */
    public int majorityElement(int[] nums) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		int maxCount = 0;
		int mode = nums[0];
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			Integer count = map.get(num) == null ? 1 : map.get(num) + 1;
			map.put(num, count);
			if (count > maxCount) {
				mode = num;
				maxCount = count;
				if (maxCount > nums.length / 2) {
					break;
				}
			}
		}
		return mode;
    }
    
	/**
	 * 167.两数之和 II - 输入有序数组 
	 * 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
	 * 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
	 * 
	 * 说明:
	 * 返回的下标值（index1 和 index2）不是从零开始的。 
	 * 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 
	 * 
	 * 示例:
	 * 输入: numbers = [2, 7, 11, 15], target = 9 
	 * 输出: [1,2] 
	 * 解释: 2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2 。
	 * 
	 * @param numbers
	 * @param target
	 * @return
	 */
	public int[] twoSum(int[] numbers, int target) {
		int i = 0;
		int num1 = numbers[0];
		int j = numbers.length - 1;
		int num2 = numbers[j];
		while (j > i && num1 != target - num2) {
			while (j > i && numbers[j] > target - num1) {
				j--;
			}
			num2 = numbers[j];
			while (j > i && numbers[i] < target - num2) {
				i++;
			}
			num1 = numbers[i];
		}
		return new int[] { i + 1, j + 1 };
	}
	
    /**
     * 160. 相交链表
     * 编写一个程序，找到两个单链表相交的起始节点。
     * 
	 *	例如，下面的两个链表：
	 *	A:          a1 → a2
	 *	                   	↘
	 *	                     c1 → c2 → c3
	 *	                   	↗            
	 *	B:     b1 → b2 → b3
	 *	在节点 c1 开始相交。
	 *
	 *	注意：
	 *	如果两个链表没有交点，返回 null.
	 *	在返回结果后，两个链表仍须保持原有的结构。
	 *	可假定整个链表结构中没有循环。
	 *	程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		Set<Integer> set = new HashSet<Integer>();
		ListNode cur = headA;
		while (cur != null) {
			set.add(cur.hashCode());
			cur = cur.next;
		}
		cur = headB;
		while (cur != null) {
			if (!set.add(cur.hashCode())) {
				return cur;
			}
			cur = cur.next;
		}
		return null;
    }
    
}
